﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Runtime.InteropServices.JavaScript.JSType;

public class Solution31
{
    public void NextPermutation(int[] nums)
    {
        //找到右边较大的，和左边较小的，这样字典序就会变大，而且要把右边的从小到排序，升序
        //较大数还要大于较小数，4，5，3，6，2，1,较大数也可以是最大数
        //较大较小和谁比较?最大的数

        int len = nums.Length;
        int biggest = 0;
        //int bigger = 0;
        int smaller = 0;

        int right = len - 1;
        //找最大值，最大值前面是较小值,严格增大
        while (right > 0 && nums[right] <= nums[right - 1])
        {
            right--;
        }

        biggest = right;
        if (biggest > 0)
        {
            smaller = biggest - 1;
        }
        int bigger = 0;
        //smaller==0，bigger==biggest
        for (int i = len - 1; i >= 0; i--)
        {
            if (nums[i] > nums[smaller])
            {
                bigger = i; break;
            }
        }

        Console.WriteLine("Bigest:   " + biggest + "  smaller:   " + smaller + "  bigger:   " + bigger);
        Console.WriteLine("Bigest:   " + nums[biggest] + "  smaller:   " + nums[smaller] + "  bigger:   " + nums[bigger]);
        Swap(nums, smaller, bigger);
        //bigeest后面的本来就是降序，所以变为升序就是反转
        int left = biggest;
        int end = len - 1;
        while (left < end)
        {
            Swap(nums, left, end);
            left++;
            end--;
        }
    }

    private void Swap(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void NextPermutation2(int[] nums)//123465
    {
        //先找6
        int Bigest = 0;
        int smaller = 0;//4
        int bigger = 0;//5

        for (int i = nums.Length - 1; i > 0; i--)
        {
            if (nums[i] > nums[i - 1])//Bigest后面的数是降序
                                      //i=0,i-1<0,说明已经是最大的，654321
            {
                Bigest = i;
                smaller = i - 1;//=4
                break;
            }
        }

        //if (Bigest == 0)//说明逆序了
        //{
        //    Reverse(nums, Bigest);
        //    return;
        //}

        for (int i = nums.Length - 1; i >= 0; i--)
        {
            if (nums[i] > nums[smaller])//bigger后面的数都小于smaller，所以交换之后也是降序
            {
                bigger = i;//5
                swap(nums, bigger, smaller);//123465->123564

                break;
            }
        }
        Console.WriteLine("Bigest:   " + nums[Bigest] + "  smaller:   " + nums[smaller] + "  bigger:   " + nums[bigger]);

        //123564,变为1235 46，从Bigest开始逆序
        Reverse(nums, Bigest);
    }

    private void Reverse(int[] nums, int start)//反转数组
    {
        int left = start;
        int right = nums.Length - 1;
        while (left < right)
        {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    private void swap(int[] nums, int bigger, int smaller)
    {
        int temp = nums[smaller];
        nums[smaller] = nums[bigger]; nums[bigger] = temp;
    }
}

internal class Program21
{
    private static void Main31(string[] args)
    {
        Solution31 solution = new Solution31();
        int[] nums = [5, 1, 1];
        solution.NextPermutation(nums);
        for (int i = 0; i < nums.Length; i++)
        {
            Console.WriteLine(nums[i]);
        }
    }
}